昨天用一題介紹了 DFS / BFS 的概念，那題雖然簡單，但是正因為簡單能幫助我們聚焦在想要展示的遍歷算法。
今天會抽幾題和 DFS / BFS 相關的題目來介紹，題目的內容可能較昨天那題花俏，但不出 DFS / BFS 的範圍，只要想清楚怎麼遍歷，

Number of Enclaves

題目給定一個二維陣列組成的圖，0 表示海，1 表示陸地，題目要求回傳沒有和邊緣四方向相鄰的陸地數量。
以範例 1 來說，就是中間三塊沒有和邊緣相鄰的陸地。

這種類型的題目可以看出來本質還是走訪，只是思路上繞了一下，希望我們算沒有與邊緣相連的陸地數量。
反過來想，我們是不是能夠直接把和邊緣相鄰的陸地去掉，剩下的陸地就是我們的目標了？
這類題目其實很多，技巧點在於如何選出 / 留下 需要的目標，排除不需要的目標。

實作方式就是從四個邊緣直接相鄰的所有陸地用 DFS / BFS 走訪相連陸地，並把所有陸地標示為 0(海洋，非目標)，最後再遍歷一次修改過後的二維陣列，就能算出答案。
程式碼如下。

public class Solution {
    public int[][] dirs = new int[][]{
        new int[]{1, 0},
        new int[]{-1, 0},
        new int[]{0, 1},
        new int[]{0, -1},
    };
    public int NumEnclaves(int[][] grid) {
        var height = grid.Length;
        var width = grid[0].Length;
        for(var i = 0; i < height; i++){
            if(grid[i][0] == 1){
                DFS(grid, i, 0);
            }
            if(grid[i][width - 1] == 1){
                DFS(grid, i, width - 1);
            }
        }
        for(var i = 0; i < width; i++){
            if(grid[0][i] == 1){
                DFS(grid, 0, i);
            }
            if(grid[height - 1][i] == 1){
                DFS(grid, height - 1, i);
            }
        }
        return grid.Sum(x=> x.Count(y => y == 1));
    }

    public void DFS(int[][] grid, int row, int col){
        if(row < 0 || col < 0 || row >= grid.Length || col >= grid[0].Length){
            return;
        }
        if(grid[row][col] == 0){
            return;
        }
        grid[row][col] = 0;
        foreach(var dir in dirs){
            DFS(grid, row - dir[0], col - dir[1]);
        }
    }
}

我是用 DFS 來寫這題，大部分題目沒特別要求我會習慣 DFS 的遍歷方式。
可以看到這種邊緣遍歷的例子，有一個比較漂亮的寫法是，四個邊緣實際上只需兩個迴圈，左右共用一個迴圈，上下共用一個迴圈，效率儘管沒有差別，會讓程式碼看起來比較舒服。

Surrounded Regions

這題和上題正好做個對比，看起來很類似，操作有些差異。
題目給一個由 O 和 X 組成的二維陣列圖，要求將被 X 包圍的 O 改為 X，而只要該 O 和邊緣相連相鄰，則不會被 X 包圍，所以是上面那題的反過來的邏輯。

這題的技巧點在於我們能把陣列裡的部分值暫時修改為特異值，之後再改回來。
邏輯是這樣的，和上題一樣，我們將和邊緣相鄰的格子，改為 # (有別於 O 和 X)，我們賦予 # 的意義是就是有和邊緣相連的 O，也就是題目最後回傳時要求保留為 O 的目標。
這時，剩下的 O 都是孤立不和邊緣相連的，我們按題目要求把這些 O 改為 X。
最後再把 # 翻回來變成 O，這題就完成了。

思考的點一樣是怎麼保留題目要求的格子、排除不要的格子。
大致上程式碼的概念和上題大同小異，只差在標示為特異值和最後的翻轉回正常值的步驟。

public class Solution {
    public int[][] dirs = new int[][]{
        new int[]{1, 0},
        new int[]{-1, 0},
        new int[]{0, 1},
        new int[]{0, -1},
    };
    public void Solve(char[][] grid) {
        var height = grid.Length;
        var width = grid[0].Length;
        for(var i = 0; i < height; i++){
            if(grid[i][0] == 'O'){
                DFS(grid, i, 0);
            }
            if(grid[i][width - 1] == 'O'){
                DFS(grid, i, width - 1);
            }
        }
        for(var i = 0; i < width; i++){
            if(grid[0][i] == 'O'){
                DFS(grid, 0, i);
            }
            if(grid[height - 1][i] == 'O'){
                DFS(grid, height - 1, i);
            }
        }

        for(var i = 0; i < height; i++){
            for(var j = 0; j < width; j++){
                if(grid[i][j] == 'O'){
                    grid[i][j] = 'X';
                }
                if(grid[i][j] == '#'){
                    grid[i][j] = 'O';
                }
            }
        }
    }

    public void DFS(char[][] grid, int row, int col){
        if(row < 0 || col < 0 || row >= grid.Length || col >= grid[0].Length){
            return;
        }
        if(grid[row][col] == 'X' || grid[row][col] == '#'){
            return;
        }
        grid[row][col] = '#';
        foreach(var dir in dirs){
            DFS(grid, row - dir[0], col - dir[1]);
        }
    }
}

我是直接用上面那題的程式碼小改一下就可以直接拿來套用了。
如說明的那段提到的，邏輯幾乎一模一樣。

Pacific Atlantic Water Flow

最後再來看一題用遍歷處理的相關題目。
題目給出一個高度表，水會由高流到低，數字越大表示越高。
上、左邊緣和 Pacific Ocean 相連，下、右邊緣和 Atlantic Ocean 相鄰，要求我們回傳那些格子的水能夠同時流到 Pacific Ocean 和 Atlantic Ocean。

正攻法的話第一時間想的應該就是去對每個格子做檢查，能不能流到 Pac 或 Atl，然後再把兩個都能流到的回傳。
但可以想見，這樣要去對每個格子重複的 DFS 做流域判斷、當中計算必定有重複的，如果真的這樣寫，最後在測資大一點的時候，就會超時。

那反過來呢，我們能不能分別做，先從 Pac (左、上邊界)開始逆流而上，最後停在的高點組 A 就是能流到 Pac 的格子。再從 Atl 逆流而上，最後停在的高點組 B 就是能流到 Atl 的格子。
這下我們只要把兩個共有的格子做比對，兩個都能流到的格子，就是題目所求，回傳對應的格子即可。

程式碼如下。

public class Solution {
    public bool[][] ToPac;
    public bool[][] ToAtl;
    public int[][] Dirs = new int[][]{
        new int[]{0, 1},
        new int[]{0, -1},
        new int[]{1, 0},
        new int[]{-1, 0}
    };
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        ToPac = new bool[heights.Length][];
        ToAtl = new bool[heights.Length][];
        for(var i = 0; i < heights.Length; i++){
            ToPac[i] = new bool[heights[0].Length];
            ToAtl[i] = new bool[heights[0].Length];
        }

        for(var i = 0; i < heights.Length; i++){
            DFS(heights, i, 0, 0, ToPac);
            DFS(heights, i, heights[0].Length - 1, 0, ToAtl);
        }
        for(var i = 0; i < heights[0].Length; i++){
            DFS(heights, 0, i, 0, ToPac);
            DFS(heights, heights.Length - 1, i, 0, ToAtl);
        }

        var result = new List<IList<int>>();
        for(var i = 0; i < heights.Length; i++){
            for(var j = 0; j < heights[0].Length; j++){
                if(ToPac[i][j] && ToAtl[i][j]){
                    result.Add(new List<int>{i, j});
                }
            }
        }

        return result;
    }
    public void DFS(int[][] heights, int row, int col, int lastHeight, bool[][] target){
        if(row < 0 || col < 0 || row >= heights.Length || col >= heights[0].Length){
            return;
        }
        if(target[row][col] || heights[row][col] < lastHeight){
            return;
        }
        target[row][col] = true;
        foreach(var dir in Dirs){
            DFS(heights, row - dir[0], col - dir[1], heights[row][col], target);
        }
    }
}

遍歷的技巧就在於是否反面思考，如果正攻不行，用排除法、從邊緣反遍歷等等的思路都要在腦裡閃過，找出最合適的。
這題的格子相交我們用和題目地圖等大的 bool 在做紀錄，是一個花空間節省時間的做法，否則會需要兩層迴圈去比對共有格子，看題目需求和測資量級，這種紀錄方法也能幫我們省到時間。

關於 DFS 和 BFS 相關遍歷技巧題目挑了這三題做分享，就是用不同的想法去增加遍歷的效率，讓我們能在時間內完成，聰明的遍歷。